package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.TraverseUtils;

/*
 * 
原题　
		A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).
	
	Each LED represents a zero or one, with the least significant bit on the right.
	
	
	For example, the above binary watch reads "3:25".
	
	Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
	
	Example:
	
	Input: n = 1
	Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
	Note:
	The order of output does not matter.
	The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00".
	The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".
	
题目大意
		二进制表在顶部有4个LED，表示小时（0-11），底部的6个LED表示分钟（0-59）。
	
	每个LED代表零或一个，右边的最低有效位。
	
	
	例如，上述二进制表读为“3:25”。
	
	给定一个非负整数n，表示当前LED的数量，返回手表可能代表的所有可能的时间。
	
	例：
	
	输入：n = 1
	返回：[“1:00”，“2:00”，“4:00”，“8:00”，“0:01”，“0:02”，“0:04”，“0:08” ，“0:16”，“0:32”]
	注意：
	输出顺序无关紧要。
	小时不能包含前导零，例如“01:00”无效，应为“1:00”。
	分钟必须由两位数组成，可能包含前导零，例如“10：2”无效，应为“10:02”。
	
解题思路
       当前i的sum[i] = sum[i-1]+num[i]
      i到j的元素和为 sum[j]- sum[i-1]
      
      TODO:
   @Type: 回溯法
 * @Date 2017-09-18 13：38
 */
public class _401_Binary_Watch {
	/**
	 * sum[4]：表示num数组索引0到索引4之间所有元素值的和		  //包括0,包括4
	 */
	private int[] sum;
    public _401_Binary_Watch(int[] nums) {
        if (nums==null || nums.length==0) {
        	sum = null;
        } else {
        	sum = new int[nums.length];
        	sum[0] = nums[0];
        	for (int i = 1; i < nums.length; i ++) {
        		sum[i] = sum[i-1]+nums[i];
        	}
        }
    }
    
    public int sumRange(int i, int j) {
    	if (sum == null)	return 0;
    	if (i>j || i<0 || j>=sum.length)	return 0;
    	if (i == 0)	
    		return sum[j];
    	return sum[j] - sum[i-1];
    }
    
	public static void main(String[] args) {
		_401_Binary_Watch obj = new _401_Binary_Watch(new int[] {3, 5, 2, 1, 6, 7});
		
	}

}
